#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File    : wordladder.py
@Time    : 2023/01/07 22:18:23
@Author  : 郭瑞强
@Contact : sunraing@126.com
@Version : 0.1
@License : BSD 3-Clause License
@Desc    : 词梯问题
"""
from pythonds.graphs import Graph, Vertex, State

# 构建树-构建词桶
def build_graph(word_file):
    d = {}
    g = Graph()

    with open(word_file, "r") as wfile:

        for line in wfile:
            word = line[:-1]  # 去掉最后的换行符
            for i in range(len(word)):
                bucket = word[:i] + "_" + word[i + 1 :]  # 创建词桶
                if bucket in d:
                    d[bucket].append(word)
                else:
                    d[bucket] = [word]

    # 为同一个桶中的单词添加顶点和边
    # 只是添加了有2个及以单词的词桶
    for bucket in d.keys():
        for word1 in d[bucket]:
            for word2 in d[bucket]:
                if word1 != word2:
                    g.add_edge(word1, word2)

    return g


from pythonds.basic import Queue

# 深度优先搜索-最短路径
def bfs(g: Graph, start: Vertex):
    start.set_distance(0)
    start.set_pred(None)
    vert_queue = Queue()
    vert_queue.enqueue(start)
    while vert_queue.size() > 0:
        cur_vert: Vertex = vert_queue.dequeque()
        for nbr in cur_vert.get_connections():
            if nbr.get_state() == State.unreached:
                nbr.set_state(State.reached)
                nbr.set_distance(cur_vert.get_distance() + 1)
                nbr.set_pred(cur_vert)
                vert_queue.enqueue(nbr)
        cur_vert.set_state(State.explored)


# 节点回溯
def traverse(y: Vertex):
    x = y
    while x.get_pred():
        print(x.get_id())
        x = x.get_pred()
    print(x.get_id())


# FOOL->PAGE
# test
def test():
    word_file = "fourletterwords.txt"
    graph = build_graph(word_file)
    bfs(graph, graph.get_vertex("FOOL"))
    traverse(graph.get_vertex("SAGE"))

    # print("图中以所有节点为{}".format(graph.get_vertexes()))
    # for ind, key in enumerate(graph.get_vertexes()):
    #     print(ind, key)

    print("图中以所有节点个数为{}".format(len(graph)))
    print("图中ID为TOEA的节点存储为{}".format(graph.get_vertex("TOEA")))

    # 检测没有进行图的单词
    print("以下节点不能与其它节点建立联系")
    words = graph.get_vertexes()
    cnt = 0
    with open(word_file, "r") as wf:
        for line in wf:
            word = line[:-1]
            if word not in words:
                cnt += 1
                print(cnt, word)
